#!/usr/bin/env python3
# -*- coding: UTF-8 -*-

'''
文件名称：main.py
创 建 者：yang qiang
创建日期：2020年07月12日
版    本：v1.0.0
描    述：
Copyright (C) 2020 All rights reserved.
'''


class Solution(object):
    def reorganizeString(self, S):
        N = len(S)
        A = []
        for c, x in sorted((S.count(x), x) for x in set(S)):
            if c > (N+1)/2: return ""
            A.extend(c * x)
        ans = [None] * N
        ans[::2], ans[1::2] = A[N/2:], A[:N/2]
        return "".join(ans)

